#include <bits/stdc++.h>
#include<climits> 
using namespace std;
 

//邻接矩阵
//一般适合用于存稠密图
//能快速判断两个点的权值关系

//邻接表
//一般用于村稀疏图，和Hash散列类似
//把与自身有关系的节点，以链表或者其他方式在自己节点下
//且对于有向的查找也具备优势
//但是确定两个顶点之前的权值以及连通性都较慢

template <class W>
struct Edge
{
    Edge(const W& w,int Dst)
    :_w(w)
    ,_Dsti(Dst)
    {

    }
    Edge(W &&w,int Dst)
    :_w(w)
    ,_Dsti(Dst)
    {

    }
    W _w;
    int _Dsti;
};

template <class V, class W,W MAX_W = INT_MAX >
class Graph
{
    using Edge = Edge<W>;

    std::vector<V> _vertex;          //存储顶点
    unordered_map<V, int> _IndexMap; // 顶点所对应的下标
    vector<list<Edge>> Adjacency_table;  //邻接表
    bool _IsDirection = false;

public:
    void Adjacency_table_Init(size_t n)
    {
        Adjacency_table.resize(n,list<Edge>());
    }

    //默认是无向图加边
    Graph(const V* ver,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex.reserve(n);
        for (size_t i = 0; i < n;++i)
        {
            _vertex.push_back(ver[i]);
            _IndexMap[ver[i]] = i;
        }
        Adjacency_table_Init(n);
    }
    
    Graph(const vector<V>& vertexs,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex(vertexs);
        for (size_t i = 0; i < n;++i)
        {
            _IndexMap[_vertex[i]] = i;
        }
        Adjacency_table_Init(n);
    }
    Graph(vector<V>&& vertexs,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex(vertexs);
        for (size_t i = 0; i < n;++i)
        {
            _IndexMap[_vertex[i]] = i;
        }
        Adjacency_table_Init(n);
    }
    size_t GetVertexIndex(const V&v)
    {
        //判断下是否存在这个点
        auto it = _IndexMap.find(v);
        if(it!=_IndexMap.end())
        {
            return it->second;
        }
        throw invalid_argument("invalid parameter:the Vertex is not existed.\n");
        //这里没有对不存在的点做增加处理
        return -1;
    }
    //提供添加有向边和无向边接口，该接口是覆盖性添加边。也就是对同一组边提供，后者权重会有效
    void AddEdge(const V& src,const V& dst,const W &w,bool IsDirection)
    {
        size_t SrcI = GetVertexIndex(src);
        size_t DstI = GetVertexIndex(dst);

        Adjacency_table[SrcI].push_back(Edge(w,DstI));
        if(!IsDirection)
        {
            Adjacency_table[DstI].push_back(Edge(w, SrcI));
        }
    }
    //提供默认接口，让用户选择默认添加什么边
    void AddEdge(const V& src,const V& dst,const W &w)
    {
        size_t SrcI = GetVertexIndex(src);
        size_t DstI = GetVertexIndex(dst);
 
        Adjacency_table[SrcI].push_back(Edge(w,DstI));
        if(!_IsDirection)
        {
            Adjacency_table[DstI].push_back(Edge(w, SrcI));
        }
    }
    //为了使得调用时构建单一的无向图或者有向图，提供两个常量以供使用
    bool UndirectedEdge = false;
    bool DirectedEdge = true;

    void SetAdd_EdgeIsdir(bool IsDirection)
    {
        _IsDirection = IsDirection;
    }
    void Print()
    {
        cout << "邻接图如下\n";
        for (int i = 0; i < Adjacency_table.size();i++)
        {
            cout << _vertex[i]<<":\n";
            for(const auto &l: Adjacency_table[i])
            {
                cout << "    ->" << _vertex[l._Dsti] << endl;
            }
            cout << endl;
        }
    }
};



int Test_Graph_Adjacency_table()
{
    string a[] = {"Lisa", "Annie", "Jane", "Sara","Lucy","Charlotte"};
    Graph<string, int> g(a,4);
    g.AddEdge("Lisa", "Annie", 520);
    g.AddEdge("Jane", "Sara", 1314);
    g.AddEdge("Lisa", "Jane", 100);
    g.AddEdge("Lucy", "Charlotte", 61);
    g.AddEdge("Lucy", "Sara", 61);

    g.Print();
    return 0;
}